class Solution:
    def searchMatrix(self, matrix, target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        start, end = 0, len(matrix) - 1
        i = (start + end) // 2
        while True:
            if end-start > 1:
                if matrix[i][-1] < target:
                    start = i
                    i = (start + end) // 2
                elif matrix[i][0] > target:
                    end = i
                    i = (start + end) // 2
                else:
                    return bool(matrix[i].count(target))
            else:
                return bool(matrix[start].count(target) or matrix[end].count(target))


a = Solution()
print(a.searchMatrix([[1, 3, 5, 7],
                      [10, 11, 16, 20],
                      [23, 30, 34, 50]], 3))
print(a.searchMatrix([[1, 3, 5, 7],
                      [10, 11, 16, 20],
                      [23, 30, 34, 50]], 13))